The United States brought this trespass and ejectment action, on its own behalf and as trustee for Mr. Reuben Mariano, against Ms. Grace Tsosie. The United States sought on behalf of Mr. Mariano the possession of land, known as Allotment No. 868, located in Crownpoint, New Mexico. Ms. Tsosie counterclaimed seeking a declaratory judgment that she has an unextinguished aboriginal occupancy right in the land. Both Mr. Mariano and Ms. Tsosie are members of the Navajo Tribe and the property at issue is located in Indian country.1 The district court dismissed the action sua sponte under the tribal court exhaustion doctrine. See United States v. Tsosie, 849 F. Supp. 768 (D.N.M.1994). The United States appeals, and we affirm.

The pleadings evince the following facts.2 Prior to 1864, members of the Navajo Tribe occupied the land surrounding and including what would become Allotment No. 868. From 1864 through 1868, the United States removed Navajo Indians from the land and incarcerated them at Bosque Redondo. In 1868, the United States and the Navajo Tribe entered into a treaty which recognized the Navajo Reservation and allowed Navajo Indians to return to their homeland. The events shortly after the 1868 treaty are the genesis of the rights claimed by both Mr. Mariano and Ms. Tsosie.

In 1908, the United States accepted applications for allotments outside the Treaty Reservation. That same year an application was approved for Allotment No. 868 in the name of Na tithl hi ya a/k/a Mr. Mariano; however, a patent was not issued to him until 1964 and he has never occupied the land. He asserts that he has to title to Allotment No. 868 based on the approved application and subsequently issued patent. He further asserts that he has the right to possess the land because Ms. Tsosie breached a homesite lease which allowed her to occupy it.

In 1868, Ms. Tsosie's ancestors returned from Bosque Redondo and resettled on Allotment No. 868. In 1901, her mother was born on or near Allotment No. 868 and her mother's umbilical cord is buried there, which has profound significance in Navajo custom and religion. In 1928, Ms. Tsosie's parents were married and continued living on the land. Shortly thereafter, according to Ms. Tsosie, the United States characterized Allotment No. 868 as "government land" and affirmatively allowed, encouraged and supported the continued occupancy and improvement of the land3 by her parents. In 1928, Ms. Tsosie was born on the land and has lived there to the present time.

Ms. Tsosie contends that the United States has taken several actions which contradict Mr. Mariano's asserted rights to the land. She asserts that in 1908, allotting agents violated the instructions of the Acting Commissioner of Indian Affairs when they approved Allotment No. 868 because the railroad claimed the land. She further asserts that in 1917, 1931, 1939 and 1960, the United States withdrew land containing Allotment No. 868 to address Indian settlement matters; and in 1945, the United States granted her a grazing permit for Allotment No. 868.4

In 1968, four years after the United States patented Allotment No. 868 to Mr. Mariano, the legal disputes surrounding the land began. That year Mr. Mariano signed as lessor and the parents of Ms. Tsosie signed as lessees a homesite lease approved by the United States covering one acre of land on Allotment No. 868. Lease payments were not made after 1969. In 1970, Mr. Mariano informed the Bureau of Indian Affairs (BIA) that he wished to terminate the lease and he began fencing the allotment. In 1975, Ms. Tsosie and her parents obtained a temporary restraining order from the Navajo Tribal Court which restrained Mr. Mariano from fencing the allotment and from harassing them or harming their property pending the settlement of the case; however, the case was never settled.

In 1981, Mr. Mariano filed suit against Ms. Tsosie's mother and two BIA officials seeking to eject Ms. Tsosie and her mother and to cancel the homesite lease. The United States defended the BIA officials and removed the action to federal district court. The district court dismissed the BIA officials and remanded the case to tribal court after the BIA declared that the homesite lease was null and void.5 On remand, Mr. Mariano consented to dismissal without prejudice of the ejectment claim against Ms. Tsosie's mother.

In 1992, the United States filed this trespass and ejectment action on behalf of Mr. Mariano in district court. In a carefully reasoned opinion, the district court dismissed the action sua sponte under the tribal court exhaustion doctrine. On appeal, the United States contends the exhaustion of tribal remedies is inappropriate because (1) the United States as plaintiff enjoys a special right of access to its own courts; (2) the United States has not waived its sovereign immunity; and (3) the policy behind tribal court exhaustion does not apply where tribal law and custom are irrelevant and are, in any event, preempted by Congress with respect to ownership of an Indian allotment.

While concerns of comity do not present a jurisdictional bar, we have held that a court has discretion to raise comity issues sua sponte. Smith v. Moffett, 947 F.2d 442, 445 (10th Cir.1991). "We review a dismissal on exhaustion grounds for an abuse of discretion." Texaco, Inc. v. Zah, 5 F.3d 1374, 1376 (10th Cir.1993)(citing United States v. Plainbull, 957 F.2d 724, 725 (9th Cir.1992)), aff'd after remand, Texaco, Inc. v. Hale, 81 F.3d 934 (10th Cir.1996). Under this standard the district court abuses its discretion "if it does not apply the correct law or if it rests its decision on a clearly erroneous finding of material fact." Plainbull, 957 F.2d at 725. "The proper scope of the tribal exhaustion rule, however, is a matter of law which we review de novo." Zah, 5 F.3d at 1376.

The tribal court exhaustion rule "provides that 'as a matter of comity, a federal court should not exercise jurisdiction over cases arising under its federal question or diversity jurisdiction, if those cases are also subject to tribal jurisdiction, until the parties have exhausted their tribal remedies.' " Id. (quoting Tillett v. Lujan, 931 F.2d 636, 640 (10th Cir.1991)). The rule was created "because of Congress's 'strong interest in promoting tribal sovereignty.' " Id. (citing Moffett, 947 F.2d at 444). Where comity concerns are present, "[j]urisdiction presumptively lies in the tribal court ... unless Congress has expressly limited that jurisdiction." Moffett, 947 F.2d at 444. Moreover, the exhaustion rule does not require an action to be pending in tribal court. Id.; cf. United States v. Bank of New York & Trust Co., 296 U.S. 463, 480, 56 S. Ct. 343, 348, 80 L. Ed. 331 (1936) ("Even where the District Court has acquired jurisdiction prior to state proceedings, the character and adequacy of the latter proceedings ... may require in the proper exercise of the discretion of the federal court that jurisdiction should be relinquished in favor of state administration."). Guided by these principles we now turn to the United States' contentions on appeal.

The United States first contends tribal court exhaustion is inappropriate because the federal government enjoys a special right of access to its own courts under 28 U.S.C. § 1345. Section 1345 provides that "the district courts shall have original jurisdiction of all civil actions, suits or proceedings commenced by the United States." Our assessment of this argument requires addressing three issues: 1) does the government enjoy special status; 2) does the Tribal court have concurrent jurisdiction; 3) does exhaustion meet the policy concerns set out in National Farmers Union Ins. Co. v. Crow Tribe, 471 U.S. 845, 856-57, 105 S. Ct. 2447, 2453-54, 85 L. Ed. 2d 818 (1985).

"[T]he grant of jurisdiction to the District Court in suits brought by the United States does not purport to confer exclusive jurisdiction," Bank of New York, 296 U.S. at 479, 56 S.Ct. at 348, and "leaves open the question of the propriety of its exercise in particular circumstances," id. at 480, 56 S.Ct. at 348; see also Gulf Offshore Co. v. Mobil Oil Corp., 453 U.S. 473, 479, 101 S. Ct. 2870, 2875-76, 69 L. Ed. 2d 784 (1981)("[T]he mere grant of jurisdiction to a federal court does not operate to oust a state court from concurrent jurisdiction over the cause of action."). In Colorado River Water Conservation Dist. v. United States, 424 U.S. 800, 96 S. Ct. 1236, 47 L. Ed. 2d 483 (1976), the United States brought suit under section 1345 on its own behalf and as trustee for certain Indian tribes for determination of reserved water rights. The Supreme Court admonished that " '[a]bdication of the obligation to decide cases can be justified under [the abstention] doctrine only in the exceptional circumstances where the order to the parties to repair to the state court would clearly serve an important countervailing interest.' " Id. at 813, 96 S.Ct. at 1244 (quoting County of Allegheny v. Frank Mashuda Co., 360 U.S. 185, 188-89, 79 S. Ct. 1060, 1062-63, 3 L. Ed. 2d 1163 (1959)). The Court in Colorado River determined that none of the three general categories of abstention applied,6 but held nevertheless that "there are principles unrelated to considerations of proper constitutional adjudication and regard for federal-state relations which govern in situations involving the contemporaneous exercise of concurrent jurisdictions.... These principles rest on considerations of '[w]ise judicial administration, giving regard to conservation of judicial resources and comprehensive disposition of litigation.' " Id. at 817, 96 S.Ct. at 1246 (quoting Kerotest Mfg. Co. v. C-O-Two Fire Equip. Co., 342 U.S. 180, 183, 72 S. Ct. 219, 221, 96 L. Ed. 200 (1952)) (alteration in original). The Court reasoned that "[t]here is no irreconcilability in the existence of concurrent state and federal jurisdiction," id. at 809, 96 S.Ct. at 1242, and held that the "factors here ... justify the District Court's dismissal," id. at 820, 96 S.Ct. at 1248. It is thus apparent that the district courts do not possess exclusive jurisdiction merely because the United States commences an action under section 1345.

We now turn to whether the tribal court has concurrent jurisdiction under the facts of this case. "Indian tribes retain 'attributes of sovereignty over both their members and their territory,' to the extent that sovereignty has not been withdrawn by federal statute or treaty." Iowa Mut. Ins. Co. v. LaPlante, 480 U.S. 9, 14, 107 S. Ct. 971, 975, 94 L. Ed. 2d 10 (1987)(citing United States v. Mazurie, 419 U.S. 544, 557, 95 S. Ct. 710, 717-18, 42 L. Ed. 2d 706 (1975)). The Supreme Court has "repeatedly recognized the Federal Government's longstanding policy of encouraging tribal self-government," id., and has "assiduously advocated federal abstention in favor of tribal courts," Moffett, 947 F.2d at 445 (citing LaPlante, 480 U.S. 9, 107 S. Ct. 971, 94 L. Ed. 2d 10; National Farmers, 471 U.S. 845, 105 S. Ct. 2447, 85 L. Ed. 2d 818). In determining whether the tribal court has concurrent jurisdiction, we consider the Navajo Nation's statutes. See Zah, 5 F.3d at 1377.

[g]enerally, the Navajo Tribal Code defines Navajo court civil jurisdiction to reach "[a]ll civil actions in which the defendant is a resident of Navajo Indian Country, or has caused an action to occur within the territorial jurisdiction of the Navajo Nation." Navajo Trib.Code tit. 7, § 253(2) (1986). The territorial jurisdiction of the Navajo Nation is defined to be coextensive with Navajo Indian Country. Id. § 254.

Zah, 5 F.3d at 1377 n. 4 (alternation in original). The present case clearly falls within the jurisdiction of the tribal court--it is essentially a dispute between two Navajo Indians7 over land located in Indian country.8

The Supreme Court suggested three federal policy concerns behind the tribal court exhaustion rule. See National Farmers, 471 U.S. at 856-57, 105 S.Ct. at 2453-54. In Zah, we paraphrased those concerns as: "(1) to further the congressional policy of supporting tribal self government; (2) to promote the orderly administration of justice; and (3) to obtain the benefits of tribal expertise." Zah, 5 F.3d at 1377-78. We agree with the district court's conclusion that abstention is appropriate under the National Farmers factors. Because the dispute here is between two Navajo Indians and involves land located in Navajo Indian country, we believe this case is essentially "a reservation affair" in which exhaustion of a tribal court remedy is almost always required. See id. at 1378.

The United States' decision to bring this suit on behalf of Mr. Mariano does not alter the fact that this is essentially a dispute between Indians over certain rights to land in Indian country.9 Cf. United States v. Mottaz, 476 U.S. 834, 846 & n. 9, 106 S. Ct. 2224, 2231 & n. 9, 90 L. Ed. 2d 841 (1986) (holding that suits involving an Indian's interests and rights in a previously issued allotment or patent do not require the United States to be a party). The present case is analogous to Plainbull, where the court said: "The fact that the Government is attempting to enforce federal law is immaterial. The alleged trespass was to tribal land and ... the tribal courts get the first opportunity to resolve this case." Plainbull, 957 F.2d at 728.10 Here the alleged trespass is to Mr. Mariano's allotment; in other words, the alleged trespass is to land in Indian country held by a Navajo. We therefore hold that "[t]he fact that the complainant in [this case] is the United States does not justify a departure from the rule," Bank of New York, 296 U.S. at 479, 56 S.Ct. at 348, which requires tribal court exhaustion.

The United States next contends tribal court exhaustion is inappropriate because it has not waived its sovereign immunity. " '[W]hen the United States institutes a suit, it thereby consents by implication to the full and complete adjudication of all matters and issues which are reasonably incident thereto.' " United States v. Taunah, 730 F.2d 1360, 1362 (10th Cir.1984) (quoting United States v. Martin, 267 F.2d 764, 769 (1959)). In Taunah, the United States brought a quiet title action on behalf of certain Indians against other Indians within the same family. The defendant Indians counterclaimed for equitable relief and the United States asserted the doctrine of sovereign immunity. We reasoned that "[t]he real plaintiff is not the United States," and held that an exception to sovereign immunity applied because the counterclaim did not "venture outside the subject of the original cause of action." Id. at 1362; see also 6 Charles A. Wright, Arthur R. Miller, & Mary K. Kane, Federal Practice and Procedure § 1427, at 197 (2d ed. 1990)("[W]hen the United States institutes an action, defendant may assert by way of recoupment any claim arising out of the same transaction or occurrence as the original claim in order to reduce or defeat the government's recovery."); cf. FDIC v. Hulsey, 22 F.3d 1472, 1486-87 (10th Cir.1994) (holding that a defendant may assert by way of recoupment any claim against the United States (1) arising from the same transaction or occurrence, (2) seeking relief of the same kind or nature, and (3) not in excess of the recovery sought by the United States).

The United States put at issue whether Ms. Tsosie rightfully occupied the land when it brought this action for ejectment and trespass. Moreover, Ms. Tsosie simply asserts occupancy rights against Mr. Mariano. The United States does not contend that Ms. Tsosie's counterclaim is unrelated to, or does not arise out of, the claims in its original complaint. Because Ms. Tsosie's counterclaim asserts claims and seeks relief based on issues asserted by the United States in its complaint, sovereign immunity has been waived with respect thereto.

Finally, the United States argues that the policy behind tribal court exhaustion does not apply because tribal law and custom are irrelevant in this case and, in any event, have been preempted by Congress. We are not persuaded.

The United States misconstrues Ms. Tsosie's counterclaim, asserting that she has not "allege[d] any issue of Navajo tribal law," Brief of Aplt. at 21. To the contrary, Ms. Tsosie asserts that she has an aboriginal occupancy right which implicates "Navajo custom, tradition, history, culture and common law," Tsosie, 849 F. Supp. at 774,11 notwithstanding the validity of Mr. Mariano's patent. The United States concedes that if the district court exercises jurisdiction, "where tribal custom may be implicated, the district court could in an appropriate case consult the tribal court." Brief of Aplt. at 6-7. "Adjudication of such matters by any nontribal court also infringes upon tribal law-making authority, because tribal courts are best qualified to interpret and apply tribal law." LaPlante, 480 U.S. at 16, 107 S.Ct. at 977.

The United States further argues it is "critical" that the dispute over the validity of the patent and allotment application be determined based on federal law in federal court. The Supreme Court has rejected the argument that tribal courts cannot address issues that arise under and "must be answered by reference to federal law."12 National Farmers, 471 U.S. at 852, 105 S.Ct. at 2452. The Court held that

the existence and extent of a tribal court's jurisdiction will require a careful examination of tribal sovereignty, the extent to which that sovereignty has been altered, divested, or diminished, as well as a detailed study of relevant statutes, Executive Branch Policy as embodied in treaties and elsewhere, and administrative or judicial decisions.

We believe that examination should be conducted in the first instance in the Tribal Court itself.... The risks of the kind of "procedural nightmare" that has allegedly developed in this case will be minimized if the federal court stays its hand until after the Tribal Court has had full opportunity to determine its own jurisdiction ...

Id. at 855-57, 105 S.Ct. at 2453-54 (footnotes omitted).

Accordingly, where the United States commences an ejectment and trespass action on behalf of an Indian against another Indian involving land located in Indian country, it is required to exhaust remedies in tribal court prior to initiating an action in district court.13 The district court correctly so held in this case.

We AFFIRM the decision of the district court.